package top.humbleyuan.test.demo;

import java.util.Arrays;

/**
 * @Author HumbleYuan
 * @Date 2020/4/22 17:10
 * @Des
 */
public class T3 {

    /**
     * 归并
     * @param args
     */
    public static void main(String[] args) {
        int[] nums = {7, 5, 9, 10, 1, 90, 35};

        nums = split(nums);

        System.out.println(Arrays.toString(nums));

    }

    public static int[] split(int[] nums) {
        if(nums == null || nums.length <= 1) {
            return nums;
        }

        int[] left = Arrays.copyOfRange(nums, 0, nums.length >> 1);
        int[] right = Arrays.copyOfRange(nums, nums.length >> 1, nums.length);

        // 归并
        return merge(split(left), split(right));
    }

    public static int[] merge(int[] nums1, int[] nums2) {
        int[] res = new int[nums1.length + nums2.length];
        int i = 0,j = 0;
        int count = 0;
        while(i < nums1.length || j < nums2.length) {
            if(i == nums1.length) {
                res[count++] = nums2[j++];
                continue;
            }

            if(j == nums2.length) {
                res[count++] = nums1[i++];
                continue;
            }

            res[count++] = nums1[i] > nums2[j] ? nums2[j++] : nums1[i++];
        }

        return res;


    }
}
